package Parser;

import java.io.FileDescriptor;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

import LexicalAnalyzer.Lexer;
import LexicalAnalyzer.Token;

/**
 * 
 * @author vcolegro, akanter
 *
 */

public class Parser {

	static Lexer lex;
	public Symbol root;


	/**
	 * Main method to create parser object.
	 * @param args  args[0]: the filename for C source file
	 */
	public static void main(String[] args){
		if (args.length!=1){
			System.out.println("Error: " + Arrays.deepToString(args) + "\nUsage: Parser filename\n filename, the full filepath to the C source file to parse");
			return;
		}

		try {
			Parser parser = new Parser(args[0]);
			Symbol root = parser.root;
			root = parser.parse(new NonTerminal("program"));
			System.out.println(root);
		} catch (IOException e) {
			System.err.println("File "+args[0]+" Not Found!");
		}
	}

	/**
	 * Constructor, takes in string of filename to build Lexer. 
	 * @param s
	 * @throws FileNotFoundException
	 * @throws IOException
	 */
	public Parser(String s) throws FileNotFoundException, IOException{
		this(new Lexer(s));
	}

	/**
	 * Constructor, takes in fileDescriptor to build Lexer. 
	 * @param fd file descriptor with which to build the lexer
	 */
	public Parser(FileDescriptor fd){
		this(new Lexer(fd));
	}

	/**
         * Private constructor for Parser. 
         * @param l lexer to use as source
         */
        private Parser(Lexer l){
                lex = l;
                this.root = new NonTerminal("program");
        }
        
        /**
         * Main loop to parse stream of tokens from Lexer. 
         * @param root
         * @return
         */
        public Symbol parse(Symbol root){
                Stack<Symbol> stack = new Stack<Symbol>();
                stack.push(new Terminal("$"));
                stack.push(root);
                Token current = lex.peekNextToken();
                
                Symbol top = stack.peek();
                LinkedList<Symbol> list = new LinkedList<Symbol>();  //will be a reversed list of symbols to be pushed on parse stack
                Stack<Integer> ptStack = new Stack<Integer>();
                Stack<Symbol> parentStack = new Stack<Symbol>();
                
        		while(!top.content.equals("$")){
        			if (!lex.hasNextToken()){
        				parentStack.peek().addChild(top);
        				stack.pop();
        				top=stack.peek();
        				ptStack.push(ptStack.pop()-1);
        				while(!ptStack.isEmpty() && ptStack.peek()==0){
        					parentStack.pop();
        					ptStack.pop();
        				}
        				continue;
        			}
        			if (top.content.equals("")){  //digest the epsilon transitions
        				stack.pop();
        				top=stack.peek();
        				ptStack.push(ptStack.pop()-1);
        				while(!ptStack.isEmpty() && ptStack.peek()==0){
        					parentStack.pop();
        					ptStack.pop();
        				}
        				continue;
        			}
        			
        			if (current.type==2){
        				lex.getNextToken();
        				current=lex.peekNextToken();
        				continue;
        			}
        			if (top.matches(current)){ //consume terminal tokens when they match top of symbol stack.
        				Terminal temp = new Terminal(current);
        				temp.linenumber=current.linenumber;
        				parentStack.peek().addChild(temp);
        				lex.getNextToken();
        				current = lex.peekNextToken();
        				stack.pop();
        				top=stack.peek();
        				ptStack.push(ptStack.pop()-1);
        				while(!ptStack.isEmpty() && ptStack.peek()==0){
        					parentStack.pop();
        					ptStack.pop();
        				}
        				continue;
        			}
        			else if (top.isTerminal()){ //when we've found a terminal that doesn't match, i.e. we expect something else from the program. 
        				System.out.println("Error(Line " + current.linenumber + "): Symbol "+ top + " does not match " + current.getContent());
        			}
        			else{ //need to develop current production to derive program
        				list.clear();
        				String topContent = top.content;
        				String tokenContent = current.getContent();

        				//figure out which NT top is; find production based on current, use peek if needed
        				if(topContent.equals("program")){
        					if(tokenContent.equals("int") || tokenContent.equals("float") || tokenContent.equals("void")){
        						list.add(new NonTerminal("decl-list"));
        						//program-->decl-list
        					}
        				}
        				else if(topContent.equals("decl-list") ){  //Parse declarations in order, recursively calling parse. Then adds these symbols to the main list in reverse
        					if(tokenContent.equals("int")|| tokenContent.equals("float")|| tokenContent.equals("void")){
        						list.add(new NonTerminal("rest-decl-list"));
        						list.add(new NonTerminal("declaration"));
        					}
        				}
        				
        				else if (topContent.equals("rest-decl-list")){
        					if(tokenContent.equals("int")|| tokenContent.equals("float")|| tokenContent.equals("void")){
        						list.add(new NonTerminal("decl-list"));
        					}
        					else
        						list.add(new Terminal(""));
        				}
        				
        				else if(topContent.equals("declaration")){
        					if(tokenContent.equals("int") || tokenContent.equals("float") || tokenContent.equals("void")){
        						list.add(new NonTerminal("rest-decl0"));				
        						list.add(new NonTerminal("type-specifier"));
        					}
        				}
        				else if (topContent.equals("rest-decl0")){
        					if(tokenContent.equals("*")){
        						list.add(new NonTerminal("rest-decl1"));
        						list.add(new Terminal("id", 0));
        						list.add(new Terminal("*"));
        						
        					}else if (tokenContent.equals("id")){
        						list.add(new NonTerminal("rest-decl2"));
        						list.add(new Terminal("id", 0));
        					}
        				}
        				else if (topContent.equals("rest-decl1")){
        					if(tokenContent.equals("semic")){
        						list.add(new NonTerminal("var-decl1"));  
        					}else if (tokenContent.equals("lparen")){
        						list.add(new NonTerminal("fun-decl"));
        					}
        				}
        				else if (topContent.equals("rest-decl2")){
        					if(tokenContent.equals("lbracket") || tokenContent.equals("semic")){
        						list.add(new NonTerminal("var-decl2"));
        					}
        					else if(tokenContent.equals("lparen")){
        						list.add(new NonTerminal("fun-decl"));
        					}
        				}
        				else if (topContent.equals("var-decl1")){
        					if(tokenContent.equals("semic")){
        						list.add(new Terminal("semic"));
        					}
        				}
        				else if (topContent.equals("var-decl2")){
        					if(tokenContent.equals("lbracket")){
        						list.add(new Terminal("semic"));
        						list.add(new Terminal("rbracket"));
        						list.add(new Terminal("num", 8));
        						list.add(new Terminal("lbracket"));
        					}else if (tokenContent.equals("semic")){
        						list.add(new Terminal("semic"));				
        					}
        				}
        				else if (topContent.equals("fun-decl")){
        					if(tokenContent.equals("lparen")){
        						list.add(new NonTerminal("compound-stmt"));
        						list.add(new Terminal("rparen"));
        						list.add(new NonTerminal("params"));
        						list.add(new Terminal("lparen"));
        					}
        				}
        				
        				else if(topContent.equals("var-declaration")){
        					if(tokenContent.equals("id")){
        						list.add(new Terminal("semic"));
        						list.add(new NonTerminal("rest-num"));
        						list.add(new Terminal(current));
        					}else if (tokenContent.equals("*")){
        						list.add(new Terminal("semic"));
        						list.add(new Terminal("id", 0));
        						list.add(new Terminal("*"));
        					}
        				}
        				
        				else if (topContent.equals("rest-num")){
        					if(tokenContent.equals("lbracket")){
        						list.add(new Terminal("rbracket"));
        						list.add(new Terminal("num", 8));
        						list.add(new Terminal("lbracket"));
        					}else if(tokenContent.equals("semic")){ //epsilon
        						list.add(new Terminal(""));
        					}
        				}
        				
        				else if(topContent.equals("type-specifier")){
        					if (tokenContent.equals("int")){
        						list.add(new Terminal("int"));
        					}
        					else if(tokenContent.equals("float")){
        						list.add(new Terminal("float"));
        					}
        					else if(tokenContent.equals("void")){
        						list.add(new Terminal("void"));
        					}	
        				}
        				else if(topContent.equals("param")){
        					if(tokenContent.equals("int") || tokenContent.equals("float") || tokenContent.equals("void")){	
        						list.add(new NonTerminal("rest-param0"));
        						list.add(new NonTerminal("type-specifier"));
        					}
        				}

        				else if(topContent.equals("rest-param0")){
        					if(tokenContent.equals("id")){
        						list.add(new NonTerminal("rest-param1"));
        						list.add(new Terminal(current));
        					} else if (tokenContent.equals("*")){
        						list.add(new Terminal("id", 0));
        						list.add(new Terminal("*"));
        					}
        				}
        				
        				else if(topContent.equals("rest-param1")){
        					if (tokenContent.equals("lbracket")){
        						list.add(new Terminal("rbracket"));
        						list.add(new Terminal("lbracket"));
        					} else if(tokenContent.equals("comma") || tokenContent.equals("rparen")){ //epsilon transition
        						list.add(new Terminal(""));
        					}
        				}
        				
        				else if(topContent.equals("params")){
        					if (tokenContent.equals("int") || tokenContent.equals("float")){
        						list.add(new NonTerminal("param-list"));
        					} else if(tokenContent.equals("void")){
        						list.add(new NonTerminal("rest-of-void"));
        						list.add(new Terminal("void"));
        					}
        				}
        				
        				else if(topContent.equals("rest-of-void")){
        					if(current.type==0){
        						list.add(new Terminal("id", 0));
        					}
        					else {
        						list.add(new Terminal(""));
        					}
        				}

        				else if(topContent.equals("param-list")){
        					if(tokenContent.equals("int") || tokenContent.equals("float") || tokenContent.equals("void")){
        						list.add(new NonTerminal("rest-param-list"));
        						list.add(new NonTerminal("param"));
        					} 
        					else if(tokenContent.equals("rparen")){
        						list.add(new Terminal(""));
        					}
        				}
        				
        				else if (topContent.equals("rest-param-list")){
        					if(tokenContent.equals("comma")){
        						list.add(new NonTerminal("param-list"));
        						list.add(new Terminal("comma"));
        					}
        					else if(tokenContent.equals("rparen")){
        						list.add(new Terminal(""));
        					}
        				}
        				
        				else if(topContent.equals("compound-stmt") && tokenContent.equals("lbrace")){
        					//compound-stmt-->{ local-decl statement-list }
        					list.add(new Terminal("rbrace"));
        					list.add(new NonTerminal("statement-list"));
        					list.add(new NonTerminal("local-declarations"));
        					list.add(new Terminal("lbrace"));
        				}
        				else if(topContent.equals("local-declarations")){
        					if(tokenContent.equals("int") || tokenContent.equals("float") || tokenContent.equals("void")){
        						list.add(new NonTerminal("local-declarations"));
        						list.add(new NonTerminal("var-declaration"));
        						list.add(new NonTerminal("type-specifier"));
        					}
        					else if (tokenContent.equals("semic") || tokenContent.equals("if") || tokenContent.equals("while") ||tokenContent.equals("for") || tokenContent.equals("return") || tokenContent.equals("+") ||tokenContent.equals("-") ||tokenContent.equals("!") ||tokenContent.equals("&") ||tokenContent.equals("*") ||tokenContent.equals("lparen") ||tokenContent.equals("lbrace") ||tokenContent.equals("id") ||tokenContent.equals("num") ||tokenContent.equals("real") || tokenContent.equals("rbrace")){	
        						list.add(new Terminal(""));
        					}
        				}
        				else if(topContent.equals("statement-list")){
        					if(tokenContent.equals("semic") ||tokenContent.equals("if") || tokenContent.equals("while") ||tokenContent.equals("for") || tokenContent.equals("return") || tokenContent.equals("+") ||tokenContent.equals("-") ||tokenContent.equals("!") ||tokenContent.equals("&") ||tokenContent.equals("*") ||tokenContent.equals("lparen") ||tokenContent.equals("lbrace") ||tokenContent.equals("id") ||tokenContent.equals("num") ||tokenContent.equals("real")){	
        							list.add(new NonTerminal("statement-list"));
        							list.add(new NonTerminal("statement"));
        					}
        					else if (tokenContent.equals("rbrace")){ 
        						list.add(new Terminal("")); 
        					}
        				}
        				else if(topContent.equals("statement")){
        					if(tokenContent.equals("if")){
        						list.add(new NonTerminal("if-stmt"));
        					}
        					else if(tokenContent.equals("while")){
        						list.add(new NonTerminal("while-stmt"));
        					}
        					else if(tokenContent.equals("for")){
        						list.add(new NonTerminal("for-stmt"));
        					}
        					else if(tokenContent.equals("return")){
        						list.add(new NonTerminal("return-stmt"));
        					}
        					else if(commonMatch(current) || tokenContent.equals("semic")){  
        						list.add(new NonTerminal("expression-stmt"));
        					}
        					else if(tokenContent.equals("lbrace")){
        						list.add(new NonTerminal("compound-stmt"));
        					}
        				}
        				else if (topContent.equals("expression-stmt")){
        					if(commonMatch(current)|| tokenContent.equals("semic")){
        						list.add(new Terminal("semic"));
        						list.add(new NonTerminal("optional-expression"));
        					}
        				}
        				else if (topContent.equals("if-stmt")){
        					if (tokenContent.equals("if")){
        						list.add(new NonTerminal("rest-if"));
        						list.add(new NonTerminal("if-start"));
        					}
        				}
        				else if(topContent.equals("if-start")){
        					if (tokenContent.equals("if")){
        						list.add(new NonTerminal("statement"));
        						list.add(new Terminal("rparen")); 
        						list.add(new NonTerminal("expression"));
        						list.add(new Terminal("lparen"));
        						list.add(new Terminal("if"));
        					}	
        				}
        				else if(topContent.equals("rest-if")){
        					if(tokenContent.equals("if") || tokenContent.equals("while") || tokenContent.equals("for")|| tokenContent.equals("return")|| commonMatch(current)|| tokenContent.equals("lbrace") || tokenContent.equals("rbrace")){
        						list.add(new Terminal(""));
        					}
        					else if(tokenContent.equals("else")){
        						list.add(new NonTerminal("statement"));
        						list.add(new Terminal("else"));
        					}
        				}
        				else if(topContent.equals("while-stmt")){
        					if(tokenContent.equals("while")){
        						list.add(new NonTerminal("statement"));
        						list.add(new Terminal("rparen"));
        						list.add(new NonTerminal("expression"));
        						list.add(new Terminal("lparen"));
        						list.add(new Terminal("while"));
        					}
        				}
        				else if(topContent.equals("for-stmt")){
        					if(tokenContent.equals("for")){
        						list.add(new NonTerminal("statement"));
        						list.add(new Terminal("rparen"));
        						list.add(new NonTerminal("optional-expression"));
        						list.add(new Terminal("semic"));
        						list.add(new NonTerminal("optional-expression"));
        						list.add(new Terminal("semic"));
        						list.add(new NonTerminal("optional-expression"));
        						list.add(new Terminal("lparen"));
        						list.add(new Terminal("for"));
        					}
        				}
        				else if(topContent.equals("return-stmt")){
        					if(tokenContent.equals("return")){
        						//return-stmt-->return; | return expression
        						list.add(new NonTerminal("rest-return"));
        						list.add(new Terminal("return"));
        					}
        				}
        				
        				else if (topContent.equals("rest-return")){
        					if(tokenContent.equals("semic")){
        						list.add(new Terminal("semic"));
        					}
        					else if (commonMatch(current)){
    							list.add(new Terminal("semic"));
    							list.add(new NonTerminal("expression"));
        					}
        				}
        				
        				else if(topContent.equals("optional-expression")){
        					if(commonMatch(current)){
        						list.add(new NonTerminal("expression"));
        					}
        					else if(tokenContent.equals("semic") || tokenContent.equals("rparen")){
        						list.add(new Terminal(""));
        					}
        				}
        				else if(topContent.equals("expression")){
        					if(commonMatch(current)){
        						list.add(new NonTerminal("rest-expression"));
        						list.add(new NonTerminal("or-expr"));
        					}					
        				}
        				
        				else if(topContent.equals("rest-expression")){
        					if(tokenContent.equals("=") || tokenContent.equals("+=") || tokenContent.equals("-=")){
        						list.add(new NonTerminal("rest-expression"));
        						list.add(new NonTerminal("or-expr"));
        						list.add(new NonTerminal("assignop"));
        					} else if (tokenContent.equals("rparen") || tokenContent.equals("rbracket") || tokenContent.equals("semic") || tokenContent.equals("comma")){  //epsilon transitions
        						list.add(new Terminal(""));
        					}
        				}
        				
        				else if(topContent.equals("assignop")){
        					if(tokenContent.equals("+=")){
        						list.add(new Terminal("+="));
        					}
        					else if(tokenContent.equals("-=")){
        						list.add(new Terminal("-="));
        					}
        					else if(tokenContent.equals("=")){
        						list.add(new Terminal("="));
        					}
        				}
        				else if(topContent.equals("or-expr")){
        					if(commonMatch(current)){
        						list.add(new NonTerminal("rest-of-or-expr"));
        						list.add(new NonTerminal("and-expr"));
        					}
        				}
        				else if(topContent.equals("rest-of-or-expr")){
        					if(tokenContent.equals("||")){
        						list.add(new NonTerminal("rest-of-or-expr"));
        						list.add(new NonTerminal("and-expr"));
        						list.add(new Terminal("||"));
        					}
        					else if(tokenContent.equals("rparen") || tokenContent.equals("rbracket") || tokenContent.equals("semic")|| tokenContent.equals("+=")|| tokenContent.equals("-=")|| tokenContent.equals("=") || tokenContent.equals("comma")){
        						list.add(new Terminal(""));
        					}
        				}
        				else if(topContent.equals("and-expr")){
        					if(commonMatch(current)){
        						list.add(new NonTerminal("rest-of-and-expr"));
        						list.add(new NonTerminal("relational-expr"));
        					}
        				}
        				else if(topContent.equals("rest-of-and-expr")){
        					if(tokenContent.equals("&&")){
        						list.add(new NonTerminal("rest-of-and-expr"));
        						list.add(new NonTerminal("relational-expr"));
        						list.add(new Terminal("&&"));
        					}
        					else if(tokenContent.equals("rparen") || tokenContent.equals("rbracket") || tokenContent.equals("semic")|| tokenContent.equals("+=")|| tokenContent.equals("-=")|| tokenContent.equals("=") || tokenContent.equals("||") || tokenContent.equals("comma")){
        						list.add(new Terminal(""));
        					}
        				}
        				else if(topContent.equals("relational-expr")){
        					if(commonMatch(current)){
        						list.add(new NonTerminal("rest-of-relational-expr"));
        						list.add(new NonTerminal("additive-expr"));
        					}
        				}
        				else if(topContent.equals("rest-of-relational-expr")){
        					if(tokenContent.equals(">") || tokenContent.equals(">=") || tokenContent.equals("<=")|| tokenContent.equals("<")|| tokenContent.equals("==")|| tokenContent.equals("!=")){
        						list.add(new NonTerminal("rest-of-relational-expr"));
        						list.add(new NonTerminal("additive-expr"));
        						list.add(new NonTerminal("relop"));
        					}
        					else if(tokenContent.equals("rparen") || tokenContent.equals("rbracket") || tokenContent.equals("semic")|| tokenContent.equals("+=")|| tokenContent.equals("-=")|| tokenContent.equals("=") || tokenContent.equals("||") || tokenContent.equals("&&") || tokenContent.equals("comma")){
        						list.add(new Terminal(""));
        					}
        				}
        				else if(topContent.equals("relop")){
        					if(tokenContent.equals(">=")){
        						list.add(new Terminal(">="));
        					}
        					else if(tokenContent.equals("<=")){
        						list.add(new Terminal("<="));
        					}
        					else if(tokenContent.equals("==")){
        						list.add(new Terminal("=="));
        					}
        					else if(tokenContent.equals("!=")){
        						list.add(new Terminal("!="));
        					}
        					else if(tokenContent.equals("<")){
        						list.add(new Terminal("<"));
        					}
        					else if(tokenContent.equals(">")){
        						list.add(new Terminal(">"));
        					}
        				}
        				else if(topContent.equals("additive-expr")){
        					if(commonMatch(current)){
        						list.add(new NonTerminal("rest-of-additive-expr"));
        						list.add(new NonTerminal("term"));
        					}
        					else if(tokenContent.equals(">=") ||tokenContent.equals("<=") || tokenContent.equals("==") || tokenContent.equals("!=") || tokenContent.equals("<") || tokenContent.equals(">") || tokenContent.equals("=")){
        						list.add(new Terminal(""));
        					}
        				}
        				else if(topContent.equals("rest-of-additive-expr")){
        					if(tokenContent.equals("+") || tokenContent.equals("-")){
        						list.add(new NonTerminal("rest-of-additive-expr"));
        						list.add(new NonTerminal("term"));
        						list.add(new NonTerminal("addop"));
        					}
        					else if(tokenContent.equals("rparen") || tokenContent.equals("rbracket") || tokenContent.equals("semic")|| tokenContent.equals("+=")|| tokenContent.equals("-=")|| tokenContent.equals("=") || tokenContent.equals("||")|| tokenContent.equals("&&") ||tokenContent.equals(">=") ||tokenContent.equals("<=") || tokenContent.equals("==") || tokenContent.equals("!=") || tokenContent.equals("<") || tokenContent.equals(">") || tokenContent.equals("comma") ){
        						list.add(new Terminal(""));
        					}
        				}
        				else if(topContent.equals("addop")){
        					if(tokenContent.equals("+")){
        						list.add(new Terminal("+"));
        					}
        					else if( tokenContent.equals("-")){
        						list.add(new Terminal("-"));
        					}
        				}
        				else if(topContent.equals("unaryop")){
        					if(tokenContent.equals("+")){
        						list.add(new Terminal("+"));
        					}
        					else if( tokenContent.equals("-")){
        						list.add(new Terminal("-"));
        					}
        					else if( tokenContent.equals("!")){
        						list.add(new Terminal("!"));
        					}
        					else if( tokenContent.equals("&")){
        						list.add(new Terminal("&"));
        					}
        					else if( tokenContent.equals("*")){
        						list.add(new Terminal("*"));
        					}
        				}
        				else if(topContent.equals("term")){
        					if(commonMatch(current)){
        						list.add(new NonTerminal("rest-of-term"));
        						list.add(new NonTerminal("unary-expr"));
        					}
        				}
        				else if(topContent.equals("rest-of-term")){
        					if(tokenContent.equals("+") || tokenContent.equals("-") ||tokenContent.equals("rparen") || tokenContent.equals("rbracket") || tokenContent.equals("semic")|| tokenContent.equals("+=")|| tokenContent.equals("-=")|| tokenContent.equals("=") || tokenContent.equals("||")|| tokenContent.equals("&&") ||tokenContent.equals(">=") ||tokenContent.equals("<=") || tokenContent.equals("==") || tokenContent.equals("!=") || tokenContent.equals("<") || tokenContent.equals(">") || tokenContent.equals("comma") ){
        						list.add(new Terminal(""));
        					}
        					else if(tokenContent.equals("*")||tokenContent.equals("%")||tokenContent.equals("/")){
        						list.add(new NonTerminal("rest-of-term"));
        						list.add(new NonTerminal("unary-expr"));
        						list.add(new NonTerminal("mulop"));
        					}
        				}
        				else if(topContent.equals("mulop")){
        					if(tokenContent.equals("%")){
        						list.add(new Terminal("%"));
        					}
        					else if( tokenContent.equals("/")){
        						list.add(new Terminal("/"));
        					}
        					else if( tokenContent.equals("*")){
        						list.add(new Terminal("*"));
        					}
        				}
        				else if(topContent.equals("unary-expr")){
        					if(tokenContent.equals("id") || tokenContent.equals("num") ||tokenContent.equals("real") ||tokenContent.equals("lparen")){
        						list.add(new NonTerminal("postfix-expr"));
        					}
        					else if( tokenContent.equals("+") ||tokenContent.equals("-")||tokenContent.equals("!")||tokenContent.equals("&") ||tokenContent.equals("*")||tokenContent.equals("%")||tokenContent.equals("*")){
        						list.add(new NonTerminal("unary-expr"));
        						list.add(new NonTerminal("unaryop"));
        					}
        				}
        				else if(topContent.equals("postfix-expr")){
        					if(tokenContent.equals("lparen") ||tokenContent.equals("id") || tokenContent.equals("num") ||tokenContent.equals("real")){
        						list.add(new NonTerminal("rest-postfix"));
        						list.add(new NonTerminal("primary-expr"));
        					}
        				}

        				else if(topContent.equals("rest-postfix")){
        					if(tokenContent.equals("lbracket")){
        						list.add(new Terminal("rbracket"));
        						list.add(new NonTerminal("expression"));
        						list.add(new Terminal("lbracket"));
        					} else if(tokenContent.equals("++")){
        						list.add(new Terminal("++"));
        					} else if(tokenContent.equals("--")){
        						list.add(new Terminal("--"));
        					} else if( tokenContent.equals("lbracket") ||tokenContent.equals("++")||tokenContent.equals("--")||tokenContent.equals("*") ||tokenContent.equals("/")||tokenContent.equals("%")||tokenContent.equals("+") || tokenContent.equals("-") ||tokenContent.equals("=")||tokenContent.equals("+=")||tokenContent.equals("-=") ||tokenContent.equals("rparen")||tokenContent.equals("semic")||tokenContent.equals("rbracket") || tokenContent.equals("||") ||tokenContent.equals("&&")||tokenContent.equals("<=")||tokenContent.equals(">=") ||tokenContent.equals("<")||tokenContent.equals(">")||tokenContent.equals("==") || tokenContent.equals("!=") || tokenContent.equals("comma")){  
        						list.add(new Terminal(""));
        					}
        				}

        				else if(topContent.equals("primary-expr")){
        					if(tokenContent.equals("lparen")){
        						list.add(new Terminal("rparen"));
        						list.add(new NonTerminal("expression"));
        						list.add(new Terminal("lparen"));
        					}
        					else if(tokenContent.equals("num")){
        						list.add(new Terminal(current));
        					}
        					else if(tokenContent.equals("real")){
        						list.add(new Terminal(current));
        					}
        					else if(tokenContent.equals("id")){
        						list.add(new NonTerminal("call-rem"));
        						list.add(new Terminal(current));
        					}				
        				}
        				else if(topContent.equals("call-rem")){
        					if(tokenContent.equals("lparen")){
        						list.add(new Terminal("rparen"));
        						list.add(new NonTerminal("args"));
        						list.add(new Terminal("lparen"));
        					}
        					else if(tokenContent.equals("lbracket") ||tokenContent.equals("++")||tokenContent.equals("--")||tokenContent.equals("*") ||tokenContent.equals("/")||tokenContent.equals("%")||tokenContent.equals("+") || tokenContent.equals("-") ||tokenContent.equals("=")||tokenContent.equals("+=")||tokenContent.equals("-=") ||tokenContent.equals("rparen")||tokenContent.equals("semic")||tokenContent.equals("rbracket") || tokenContent.equals("||") ||tokenContent.equals("&&")||tokenContent.equals("<=")||tokenContent.equals(">=") || tokenContent.equals("<") || tokenContent.equals(">") || tokenContent.equals("==") || tokenContent.equals("!=") || tokenContent.equals("comma")){  
        						list.add(new Terminal(""));
        					}
        				}
        				else if(topContent.equals("args")){
        					if(commonMatch(current)){
        						list.add(new NonTerminal("arg-list"));
        					}
        					else if(tokenContent.equals("rparen")){
        						list.add(new Terminal(""));
        					}
        				}
        				else if(topContent.equals("arg-list")){
        					if(commonMatch(current)){
        						list.add(new NonTerminal("rest-arg-list"));
        						list.add(new NonTerminal("expression"));
        					}
        				}
        				else if(topContent.equals("rest-arg-list")){
        					if(tokenContent.equals("comma")){
        						list.add(new NonTerminal("arg-list"));
        						list.add(new Terminal("comma"));
        					}else if (tokenContent.equals("rparen")){
        						list.add(new Terminal(""));
        					}
        				}

        			}//END PRODUCTION IF-STATEMENTS

                        if (list.isEmpty()){ //no legal derivations can develop this nonterminal    
                        		System.out.println("Error(Line " + current.linenumber + "):No production for symbol " + top.toString().replaceAll("\\s|\\(|\\)", "") + " with token " + current.getContent());
                        		System.out.println("WARNING: Attempting to finish parse - don't expect a correct parse. Try again with better input =)");
                        		lex.getNextToken();
                        		current = lex.peekNextToken();
                        		continue;
                        }
                        
                        
                        stack.pop(); //replace NT with the right hand side of the appropriate production
                        
                        if(!ptStack.isEmpty())
                        	ptStack.push(ptStack.pop()-1);
                        
                        int parentTimer = 0;
                        for(Symbol s : list){
                                stack.push(s);
                                parentTimer++;
                        }
                        ptStack.push(parentTimer);
                        
                        if(!parentStack.isEmpty())
                        	parentStack.peek().addChild(top);
                        
                        parentStack.push(top);
                        
                        top = stack.peek();

        		}
        		if (lex.hasNext()){
        			System.out.println("Error(Line "+lex.peekNextToken().linenumber+"): End of input, encountered " + lex.peekNextToken());
        			lex.getNextToken();
        			StringBuilder sb = new StringBuilder();
        			while(lex.hasNext()){
        				sb.append(lex.next().toString() + " ");
        			}
        			sb.deleteCharAt(sb.length()-1);
        			sb.append('\n');
        			System.out.println(sb);
        		}
        		return syntaxTree(root); 
        }

        /**
         * 
         * @param t the token to be matched
         * @return true if the given token's content is is +, -, !, &, *, (, id, num, real
         */
        //If token content is +, -, !, &, *, (, id, num, real
        private boolean commonMatch(Token t){
                String content = t.getContent();
                //type==0,6,7,8 refers to it being a constant. We can't test for content being "id" since that's not what is in the fields 
                return (content.equals("+") || content.equals("-") || content.equals("!") || content.equals("&") || content.equals("*") || content.equals("lparen") || t.type==0 || (t.type>=6 && t.type<=8));
        }
        
        /**
         * 
         * @param root the symbol 
         * @return a new symbol representing the root of the syntax tree.  The syntax tree will eliminate any NonTerminal without children
         * (due to epsilon transitions) or replace it with its child if it only has one.
         */
        private Symbol syntaxTree(Symbol root){
        	if (root.isTerminal()) 
        		return root;
        	if (root.getChildren().size()==1)
        		return syntaxTree(root.getChildren().get(0));
        	if (root.getChildren().size()==0)
        		return new Terminal("");
        	
        	if(root.content.equals("local-declarations") || root.content.equals("arg-list")){
        		//put type-specifier with var-declaration
        		Symbol temp = root.getChildren().remove(0);
        		root.getChildren().get(0).getChildren().add(0, temp);
        		//flatten local-declarations list        		
        	}
        	
        	if (root.content.equals("declaration")){
        		Symbol temp = root.getChildren().remove(0);
        		root.getChildren().get(0).getChildren().add(0, temp);  //LOLLERSKATEZ
        		root.content=clarifyDeclaration(root);
        	}
        	
        	ArrayList<Symbol> newChildren = new ArrayList<Symbol>();
        	Symbol temp;
        	for(Symbol child : root.getChildren()){  //recursion, each child returns its syntax sub-tree
        		temp = syntaxTree(child);
        		if(temp.content.contains("rest-") || temp.content.equals("decl-list") || temp.content.equals("if-start") || temp.content.equals("fun-decl") || temp.content.equals("var-decl1") || temp.content.equals("var-decl2")){
        			for(Symbol elt : temp.getChildren()){
        				newChildren.add(elt);
        			}
        		}
        		else if(temp.content.equals("call-rem")){
        			Symbol temp2 = newChildren.remove(newChildren.size()-1);
        			temp.content="call";
        			temp.children.add(0, temp2);
        			newChildren.add(temp);
        		}
        		
        		else{
        			if (!temp.toString().equals(""))
        			newChildren.add(temp);
        		}
        	}
        	
        	if (newChildren.size()==1){   //If newChildren has 1 element, replace this symbol with its child
        		return newChildren.get(0);
        	}
        	if (newChildren.size()==0){  //If newChildren is empty, this is a dead end symbol and is thus removed
        		return new Terminal("");
        	}
        	
        	if(root.content.equals("local-declarations")){
        		if(newChildren.get(1).content.equals("local-declarations")){
        			newChildren.get(1).getChildren().add(0,newChildren.get(0));
        			return newChildren.get(1);
        		}
        	}
        	if(root.content.equals("arg-list")){
        		if(newChildren.get(2).content.equals("arg-list")){
        			newChildren.get(2).getChildren().add(0,newChildren.get(0));
        			newChildren.get(2).getChildren().add(1,newChildren.get(1));
        			return newChildren.get(2);
        		}
        	}
        	
        	root.setChildren(newChildren);
        	return root;
        }
         
        /**
         *  @param declaration symbol to convert its contents to var-declaration or fun-declaration, depending on which it is
         *  @return 
         */
        private String clarifyDeclaration(Symbol declaration){
        	if(!declaration.isTerminal()){
        		String temp;
        		for(Symbol child : declaration.getChildren()){
        			if (child.content.equals("var-decl1") || child.content.equals("var-decl2")){
        				return "var-declaration";
        			}
        			if (child.content.equals("fun-decl")){
        				return "fun-declaration";
        			}
        			temp = clarifyDeclaration(child);
        			if(!temp.equals(""))
        				return temp;
        		}
        	}
        	return "";
        }
}